package com.fyl.leetcode.backtracking;

import java.util.ArrayList;
import java.util.List;

/**
 * @author:fyl
 * @date 2021/5/25 17:29
 * @Modified By:
 * @Modified Date:
 * @Description: 39
 * 给定一个无重复元素的数组candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。
 * candidates中的数字可以无限制重复被选取。
 * 说明：
 * 所有数字（包括target）都是正整数。
 * 解集不能包含重复的组合。
 *
 * 输入: candidates = [2,3,6,7], target = 7
 * 输出: [[7],[2,2,3]]
 */
public class CombinationSum {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        def(result,list,candidates,target,0,0);
        return result;
    }

    private void def( List<List<Integer>> result,List<Integer> list,int[] candidates,int target,int sum,int begin){
        if (sum == target){
            result.add(new ArrayList<>(list));
        }
        for (int i = begin; i < candidates.length; i++) {
            sum += candidates[i];
            list.add(candidates[i]);
            def(result,list,candidates,target, sum,begin);
            list.remove(list.size() - 1);
            sum -= candidates[i];
            def(result,list,candidates,target, sum,begin);
            list.remove(list.size() - 1);
            sum -= candidates[i];
        }
    }
}
